Problema  1  - axyz   100 puncte



Autor prof. Carmen Minc
Colegiul National de Informatic Tudor Vianu, Bucuresti

Descrierea solutiei

Cerinta 1 (30 puncte)
O solutie se poate obtine astfel:
- Parcurgem sirul cifrelor de la pozitia N ctre prima, ntrerupnd parcurgerea la prima cifr X[k] cu proprietatea c:
X[k]>X[k+1] <= X[k+2] <=...<= X[N]
- Determinm pozitia poz a celei mai mari cifre dintre cele situate pe pozitiile k+1,k+2,,N si cu proprietatea X[k]>X[poz]
- Interschimbm cifrele X[k] si X[poz].
- Sortm descresctor n vectorul X cifrele de pe pozitiile k+1,k+2,,N restul numrului nemodificndu-se. Complexitatea este dat de algoritmul de sortare folosit, maximum O(N2) -solutia obtine un punctaj partial
- Pentru a obtine o complexitate liniara (O(N)), ne vom folosi de faptul c n vectorul X cifrele de pe pozitiile k+1,k+2,,N sunt sortate cresctor. Nu are sens s le sortm descresctor,  deoarece le putem scrie n fisierul de iesire n ordine invers, solutia cutat fiind X[1], X[2],..., X[K], X[N], X[N-1],..., X[K+1]

Cerinta 2 (70 puncte)
O solutie cu punctaj maxim se poate obtine astfel:
2.1.Pentru A format din 2 cifre
      -	Separm cifrele lui A: ab, a=[A/10], b=A%10
      -	Parcurgem sirul cifrelor lui X de la pozitia N ctre prima numrnd aparitiile cifrelor b n variabila NB (initial cu valoarea 0). Variabila Z va memora numrul perechilor cerute (initial este 0). 
      -	n timpul acestei parcurgeri, se studiaz fiecare cifr astfel:
         - Dac cifra curent este egal cu b atunci o numrm ( NB=NB+1). 
         - Altfel, dac cifra curent este a atunci se pot forma cu NB numere A din cifra a curent si cele NB cifre b situate la dreapta lui a n X. Adugm numrul acestora la celelalte gsite pn n acest moment (Z=Z+NB)  

2.2.Pentru A format din 3 cifre
      -	Separm cifrele lui A: abc, a=[A/100], b=[A/10%10], c=A%10;
      -	Parcurgem sirul cifrelor lui X de la pozitia N ctre prima numrnd aparitiile cifrelor c n variabila NC (initial cu valoarea 0). La ntlnirea unei cifre b se pot genera NC numere de forma bc, astfel vom incrementa  variabila NBC (initial cu valoarea 0) cu valoarea NC. La ntlnirea unei cifre a se pot genera NBC numere de forma abc, astfel vom incrementa  variabila Z (initial cu valoarea 0) cu valoarea NBC. Variabila Z va memora numrul perechilor cerute. 
      -	n timpul acestei parcurgeri, se studiaz fiecare cifr astfel:
         - Dac cifra curent este egal cu c atunci o numrm ( NC=NC+1). 
         - Dac cifra curent este egal cu b atunci se pot forma nc NC numere de forma bc si adugm acest numr la variabila NBC ( NBC=NBC+NC). 
         - Altfel, dac cifra curent este a atunci se pot forma cu NBC numere A din cifra a curent si cele NBC numere bc situate la dreapta lui a n X. Adugm numrul acestora la celelalte gsite pn n acest moment (Z=Z+NBC)  

-	Complexitate O(N)



